import numpy as np
import math
from SAGIN_Progrem.entity.Appliances import Appliances
from SAGIN_Progrem.entity.Structure import Queue
from SAGIN_Progrem.entity.Formulas import Formulas
import random
from threading import Lock, Thread
import threading

def random_a():
    if random.random() < 0.5:
        a = 1       # 卸载
    else:
        a = 0       # 本地
    return a

# 无人机
class UAV:
    fly_speed = 23  # 无人机飞行速度25米每秒
    B = 1000000  # 带宽1MHz
    P = 30  # 传输功率 30dBm
    f = 2800000000  # CPU频率 1GC/s
    formulas = Formulas(B, P, f)
    uav_R = 23 # 无人机的覆盖半径

    def __init__(self, id):
        self.id = id
        # self.wait_queue = Queue(40)
        self.computing_queue = Queue(12)
        self.offloading_sa_queue = Queue(10)
        self.offloading_cloud_queue = Queue(10)
        self.cover_list = []  # 被无人机覆盖的传感器id列表
        self.coordinates_x_y = []
        self.uav_off_num = 0 # 无人机卸载个数
        self.uav_lo_num = 0 # 无人机本地计算个数

    # 判断UAV覆盖范围内有多少设备，以无人机初始位置为圆心，半径100米，利用圆的方程，例：x^2+y^2=1
    def cover(self, app_list):
        uav_cov_list = []
        # print(app_list)
        for i in range(0, len(app_list)):
            if (app_list[i].coordinates_x_y[0] - self.coordinates_x_y[0]) ** 2 + (
                    app_list[i].coordinates_x_y[1] - self.coordinates_x_y[1]) ** 2 <= self.uav_R ** 2:
                if not app_list[i].flag:
                    app_list[i].flag = True
                    uav_cov_list.append(app_list[i].id)
                # app_list[i].flag = True
                # uav_cov_list.append(app_list[i].id)
        return uav_cov_list  # 返回在服务范围内传感器的id

    # 更新无人机所在位置的方法
    def reset_coordinates_x_y(self, theta):
        angle = math.radians(theta)  # 将角度转换为弧度
        ux = math.cos(angle)
        uy = math.sin(angle)
        dx = ux * self.fly_speed
        dy = uy * self.fly_speed
        self.coordinates_x_y[0] = self.coordinates_x_y[0] + dx
        self.coordinates_x_y[1] = self.coordinates_x_y[1] + dy
        return self.coordinates_x_y  # 返回新的坐标点

    # 返回无人机下一时刻的位置
    def get_next_coordinates_x_y(self, theta):
        angle = math.radians(theta)  # 将角度转换为弧度
        ux = math.cos(angle)
        uy = math.sin(angle)
        dx = ux * self.fly_speed
        dy = uy * self.fly_speed
        coordinates_x_y = [[], []]
        coordinates_x_y[0] = self.coordinates_x_y[0] + dx
        coordinates_x_y[1] = self.coordinates_x_y[1] + dy
        return coordinates_x_y  # 返回新的坐标点

    # 无人机收集任务：无人机收集任务时对计算队列机型检测，若计算队列不满，则放入计算队列，若满，则放入卸载队列
    def collect_c(self, task_list,  step_time):  # task是待传入数据的集合
        round_ = step_time
        # lock = Lock()
        termination = len(task_list)
        arrive_time_list = []
        arrive_time = 0
        for i in range(len(task_list)):
            if task_list[i].flag == 0:
                delay = round(self.formulas.transmission_Delay(task_list[i]), 2)
                arrive_time += delay
                if arrive_time <= round_:
                    arrive_time_list.append(arrive_time)
                    task_list[i].flag = 1
                    task_list[i].arrive_time = arrive_time
                    task_list[i].delay['transmission'] += delay
                    round_ -= delay
                    termination -= 1
        return arrive_time_list
        # print('uav{}_collect_end\n'.format(self.id))

    # 无人机任务向云服务器卸载，卸载到卫星的卸载队列
    def off_to_sate_o(self, task_list, app_list, step_time):
        round_ = step_time
        delay_w_temp = 0  # 用于记录等待时间
        # lock = Lock()
        off_cloud_list = []
        num = 0
        while True:
            while not self.offloading_cloud_queue.isMAX():
                if num < len(task_list):
                    self.offloading_cloud_queue.enQueue(task_list[num])
                    num += 1
                else:
                    break
            for i in range(0, self.offloading_cloud_queue.size()):
            # with lock:
                task = self.offloading_cloud_queue.get_hand()
                task_index = task.get_task_index()
                delay = round(self.formulas.transmission_sa_Delay(task), 2)
                if round_ >= delay:
                    app_list[task.id].task_app_one_list[task_index].delay['wait'] += delay_w_temp
                    app_list[task.id].task_app_one_list[task_index].delay['transmission'] += delay
                    delay_w_temp += self.formulas.transmission_Delay(task)  # 等待延迟更新
                    # sate.offloading_queue.enQueue(self.offloading_cloud_queue.get_hand())
                    off_cloud_list.append(task)
                    self.offloading_cloud_queue.deQueue()
                    self.uav_off_num += 1
                    round_ -= delay
                    # print('uav__off')
                else:
                    for j in range(0, self.offloading_cloud_queue.size()):
                        self.offloading_cloud_queue.items[j].delay['wait'] += delay_w_temp
                    return off_cloud_list
            if num >= len(task_list):
                return off_cloud_list
        # print('uav{}_off_to_cloud_end\n'.format(self.id))

    # 无人机任务向卫星卸载，卸载到卫星的计算队列
    def off_to_sate_c(self, task_list, step_time):
        round_ = step_time
        delay_w_temp = 0  # 用于记录等待时间
        off_sa_list = []
        num = 0
        while True:
            while not self.offloading_sa_queue.isMAX():
                if num < len(task_list):
                    self.offloading_sa_queue.enQueue(task_list[num])
                    num += 1
                else:
                    break
            for i in range(0, self.offloading_sa_queue.size()):
            # with lock:
                task = self.offloading_sa_queue.get_hand()
                task_index = task.get_task_index()
                delay = round(self.formulas.transmission_sa_Delay(task), 2)
                if round_ >= delay:
                    task.delay['wait'] += delay_w_temp
                    task.delay['transmission'] += delay
                    delay_w_temp += self.formulas.transmission_Delay(task)  # 等待延迟更新
                    # sate.computing_queue.enQueue(self.offloading_sa_queue.get_hand())
                    off_sa_list.append(task)
                    self.offloading_sa_queue.deQueue()
                    self.uav_off_num += 1
                    round_ -= delay
                    # print('uav__off')
                else:
                    for j in range(0, self.offloading_sa_queue.size()):
                        self.offloading_sa_queue.items[j].delay['wait'] += delay_w_temp
                    return off_sa_list
            if num >= len(task_list):
                return off_sa_list

    # 卸载机制
    def off_idea(self, off_num, off_sa_num, off_cloud_num):
        flag = True
        place = 0
        if self.offloading_sa_queue.isMAX() and self.offloading_cloud_queue.isMAX():
            return flag, off_num, off_sa_num, off_cloud_num
        else:
            if off_num > 0:
                flag = False
                self.uav_off_num += 1
                a = random_a()
                # if off_sa_num > 0 and not self.offloading_sa_queue.isMAX() and (self.offloading_cloud_queue.isMAX() or a == 0):  # 卸载到卫星
                if off_sa_num > 0 and (off_cloud_num == 0 or a == 0):  # 卸载到卫星
                    # self.offloading_sa_queue.enQueue(self.computing_queue.get_hand())
                    # self.computing_queue.deQueue()
                    place = 2
                    off_sa_num -= 1
                    off_num -= 1
                elif off_cloud_num > 0 and (off_sa_num == 0 or a == 1):  # 卸载到云服务器
                    # self.offloading_cloud_queue.enQueue(self.computing_queue.get_hand())
                    # self.computing_queue.deQueue()
                    place = 3
                    off_cloud_num -= 1
                    off_num -= 1
                else:
                    flag = True
            return flag, off_num, off_sa_num, off_cloud_num, place


    # 无人机普通计算队列的本地计算，版本2
    def compute_task_n2(self, arrive_time_list, task_list, app_list, step_time, action): # 动作集：（卸载比例， 卸载向卫星卸载的比例）
        round_ = step_time
        delay_w_temp = 0  # 用于记录等待时间
        off_num = round(action[0] * len(arrive_time_list))
        off_sa_num = round(action[1] * off_num)
        off_cloud_num = off_num - off_sa_num
        num = 0
        off_cloud_list = []
        off_sa_list = []
        while True:
            # with lock:
            while not self.computing_queue.isMAX():
                if num < len(arrive_time_list):
                    self.computing_queue.enQueue(task_list[num])
                    num += 1
                else:
                    break
            while not self.computing_queue.isEmpty():
                # 无人机计算队列空不卸载，卸载队列满,不卸载
                flag, off_num, off_sa_num, off_cloud_num, place = self.off_idea(off_num, off_sa_num, off_cloud_num)
                if place == 2:
                    off_cloud_list.append(self.computing_queue.get_hand())
                    self.computing_queue.deQueue()
                if place == 3:
                    off_sa_list.append(self.computing_queue.get_hand())
                    self.computing_queue.deQueue()
                if flag:
                    task = self.computing_queue.get_hand()
                    task_index = task.get_task_index()
                    delay = self.formulas.compute_Delay(task)
                    if round_ >= delay:
                        if not app_list[task.id].task_app_one_list[task_index].delay['wait'] == 0:
                            app_list[task.id].task_app_one_list[task_index].delay['wait'] -= app_list[task.id].task_app_one_list[task_index].arrive_time
                            app_list[task.id].task_app_one_list[task_index].arrive_time = 0
                        app_list[task.id].task_app_one_list[task_index].delay['wait'] += delay_w_temp
                        app_list[task.id].task_app_one_list[task_index].delay['compute'] += round(delay, 2)
                        app_list[task.id].task_app_one_list[task_index].finish = 1
                        app_list[task.id].task_app_one_list[task_index].size_ = app_list[task.id].task_app_one_list[task_index].size
                        delay_w_temp += round(delay, 2)
                        self.computing_queue.deQueue()
                        self.uav_lo_num += 1
                        round_ -= delay
                    else:
                        app_list[task.id].task_app_one_list[task_index].delay['compute'] += round_
                        delay_w_temp += round_
                        size_down = ((round_ / 1000) * self.f) / task.complex
                        app_list[task.id].task_app_one_list[task_index].size_ -= size_down
                        for j in range(0, self.computing_queue.size()):
                            self.computing_queue.items[j].delay['wait'] += delay_w_temp
                        while not self.computing_queue.isMAX():
                            if num < len(arrive_time_list):
                                self.computing_queue.enQueue(task_list[num])
                                num += 1
                            else:
                                return off_sa_list, off_cloud_list
                        return off_sa_list, off_cloud_list
            if num >= len(arrive_time_list):
                return off_sa_list, off_cloud_list

    def compute_task_n2_(self, arrive_time_list, task_list, step_time, action, step): # 动作集：（卸载比例， 卸载向卫星卸载的比例）
        round_ = step_time
        delay_w_temp = 0  # 用于记录等待时间
        off_num = round(action * len(arrive_time_list))
        local_num = len(arrive_time_list) - off_num
        num = 0
        off_sa_list = task_list[local_num:]
        arrive_time_list = arrive_time_list[:local_num]
        while True:
            while not self.computing_queue.isMAX():
                if num < len(arrive_time_list):
                    self.computing_queue.enQueue(task_list[num])
                    num += 1
                else:
                    break
            while not self.computing_queue.isEmpty():
                # 无人机计算队列空不卸载，卸载队列满,不卸载
                task = self.computing_queue.get_hand()
                task_index = task.get_task_index()
                delay = self.formulas.compute_Delay(task)
                if round_ >= delay:
                    if not task.delay['wait'] == 0:
                        task.delay['wait'] -= \
                        task.arrive_time
                        task.arrive_time = 0
                    task.delay['wait'] += delay_w_temp
                    task.delay['compute'] += round(delay, 2)
                    task.finish = 1
                    task.finish_step = step
                    task.size_ = task.size
                    delay_w_temp += round(delay, 2)
                    self.computing_queue.deQueue()
                    self.uav_lo_num += 1
                    round_ -= delay
                else:
                    task.delay['compute'] += round_
                    delay_w_temp += round_
                    size_down = ((round_ / 1000) * self.f) / task.complex
                    task.size_ -= size_down
                    for j in range(0, self.computing_queue.size()):
                        self.computing_queue.items[j].delay['wait'] += delay_w_temp
                    while not self.computing_queue.isMAX():
                        if num < len(arrive_time_list):
                            self.computing_queue.enQueue(task_list[num])
                            num += 1
                        else:
                            return off_sa_list
                    return off_sa_list
            if num >= len(arrive_time_list):
                return off_sa_list

    # 判断坐标是否在范围内
    def coor_right(self):
        if self.coordinates_x_y[0] < 0:
            return True
        elif self.coordinates_x_y[1] < 0:
            return True
        elif self.coordinates_x_y[0] > 300:
            return True
        elif self.coordinates_x_y[1] > 300:
            return True
        else:
            return False

    # 列表去重
    def unique_list(self, lit):
        return list(set(lit))

    # 无人机对等待队列中的任务进行分配
    def distribute(self, action):
        for i in action:
            if not self.wait_queue.isEmpty():
                if i:
                    self.wait_to_off()
                else:
                    self.wait_to_cumpute_n()
            else:
                break
        pass

if __name__ == '__main__':
    uav_coor_list_PSO = [[120, 160], [250, 225], [10, 280], [275, 50], [40, 23],
                         [97.16527530655293, 162.75233504037544], [232.9437912018936, 209.56997273380898],
                         [21.478279182274115, 260.06889097381253], [254.1135076714596, 59.63091055974577],
                         [43.50793221931641, 0.26908687393571284], [74.28525963160251, 165.0985836874765],
                         [215.1186502693875, 195.03503720810758], [39.94198503402635, 246.35424310301502],
                         [276.87452955838893, 56.323965948367714], [20.773652619708397, -3.216961187529716],
                         [58.198340900752356, 181.53668107577002], [200.08995503625786, 212.44590506670977],
                         [61.708821393255135, 253.7842387228358], [296.8273245180621, 44.88342517018589],
                         [1.118894646429446, 8.728351240859396], [35.31176454918726, 179.2553168120056],
                         [182.53047577179794, 197.59111836474054], [82.11576406515, 264.393512533328],
                         [286.86150595943724, 24.154641789182342], [23.713170724889594, 4.42734106994332],
                         [17.07727631899272, 165.23734837920847], [187.05062741890578, 175.03966100413635],
                         [103.74472085169401, 272.2158030115583], [284.8829991957078, 1.2398973876866783],
                         [1.617620861700484, 10.813785796340298], [4.506615851710158, 184.49815042419868],
                         [200.73312624258972, 156.5521185514498], [89.18828553473915, 254.40821499792466],
                         [261.89907819753194, 0.38002789200094433], [23.273470413731516, 3.0662584372535804],
                         [19.425993286463452, 166.99351741006856], [220.02951658286452, 169.06808115269425],
                         [111.88111265791592, 258.15462623504385], [242.1065477945043, 12.095647390995724],
                         [2.438018547636325, 12.807097494317933], [32.2374256915212, 186.09501472652613],
                         [199.33200546539132, 159.03747630841525], [134.2789498421106, 252.9261571024673],
                         [221.11677341627208, 21.499336643140634], [23.68440760841037, 3.9985248586282545],
                         [9.412656378316171, 188.92872356812822], [176.9479281155426, 164.3245436614939],
                         [149.47046774483684, 270.19514039075466], [202.75853723437012, 35.35484689320019],
                         [46.28659636331557, -0.26070787598922607], [-0.49432066417533527, 209.68569362349868],
                         [155.66911788146967, 155.5945817473551], [161.5763516898933, 250.63887352029025],
                         [181.8087820979154, 25.862336175661376], [67.62493442069251, 8.322725524993093],
                         [5.553737295276878, 231.87625456546468], [173.41857305235155, 170.22184537172637],
                         [182.2108755516548, 260.79842198458704], [173.13914882070205, 47.16579736952926],
                         [87.5997161812133, 19.72483469915759], [0.08211936806814446, 209.53657244465893],
                         [154.88211172285457, 183.8379975954665], [199.21845885098477, 276.2820297785203],
                         [150.2945490835269, 49.83492884779277], [86.5563333646953, 42.7011562563215],
                         [5.89503761728441, 231.78988638725923], [153.76485401243892, 206.81084537732664],
                         [191.861382425865, 298.07362050694], [134.79633698532223, 32.840652700834866],
                         [103.58347284809709, 58.163255758419524], [19.46624569315752, 213.22049459966004],
                         [171.49797622320506, 221.45790571918474], [214.73955237602968, 295.70944205949104],
                         [142.30515982968808, 11.100883164523548], [112.11308873679776, 79.52316336101053],
                         [35.61739410298769, 229.59548788343395], [151.67111696762976, 209.8004766690207],
                         [237.61862383804376, 293.3540038760414], [119.78799149318144, 6.412905977567269],
                         [93.6432187087559, 65.81681807325272], [54.982787320723375, 242.00441795505884],
                         [160.9016796383849, 188.73399350781742], [260.6185516645882, 293.2963846626936],
                         [142.7750758517543, 7.1835892405578425], [100.80511254722055, 87.6733337298381],
                         [64.96030559423016, 221.2812635353804], [141.90943988459983, 175.7611438156817],
                         [261.3926116085835, 270.3094137617005], [124.2014840981636, -6.381870182954052],
                         [87.07111385288192, 106.12265024465526], [54.6534672660515, 200.71991426844784],
                         [144.9476014235835, 198.55959934370026], [282.57422890713383, 261.3462062656223],
                         [136.08187962829027, 13.312194964895596], [67.66986776881461, 118.47544953815401],
                         [64.85194556593137, 180.10460344452673], [163.1537770474625, 212.61431987284897],
                         [264.3325415638645, 247.33760737528334], [158.3595798360862, 19.03094250710876],
                         [44.88369358486749, 115.34650945262639], [86.71355754820115, 172.95828120601283],
                         [161.0601345757759, 235.51883168167717], [263.24756721593457, 224.36321226541517],
                         [181.31971976392254, 20.38444703025447], [21.89390354168191, 116.03174938888623],
                         [98.45749703619275, 153.18254138919707], [182.2743322089584, 244.4046529031667],
                         [282.74299519402933, 212.1595944431905], [194.32464786586092, 39.354735511545755],
                         [44.876209717384455, 116.93374874934325], [79.2678443029891, 165.86154876276737],
                         [177.61392493970015, 266.9275435720983], [292.8950098956859, 191.52136299043883],
                         [185.32629188819666, 60.52144497946338], [33.84161435071235, 96.753617305425],
                         [102.26784430296257, 165.8615138327352], [188.76943139003887, 246.81399898551555],
                         [279.973379154794, 172.49423869389742], [207.27594141586005, 67.39260831711927],
                         [14.13986043284405, 108.62125786957088], [120.45506172599926, 151.7822694493462],
                         [166.61473242828146, 240.63586707417656], [295.12773441924963, 155.19263424463708],
                         [228.80880862230896, 75.47565414585469], [36.317325130651355, 102.52535272123478]]
    uav_coor_list_SCA = [[120, 160], [250, 225], [10, 280], [275, 50], [40, 23],
                         [97.09621890321661, 162.10162115297402], [232.08446866158204, 210.57662533031316],
                         [19.232715560792325, 258.93446028762844], [254.10730166479354, 59.61744021421816],
                         [53.18086962145343, 4.151533854919492], [120.09621890321661, 162.10162115297402],
                         [221.13011663480222, 190.35282322305883], [37.245188416464174, 244.6323338155375],
                         [265.84271866253357, 39.83664174981956], [76.18086962145344, 4.151533854919492],
                         [97.10608941075687, 162.77537624195858], [229.7584187839952, 211.67305779077014],
                         [59.73057699586944, 249.4704429950777], [286.70515945877986, 49.51954234949101],
                         [99.18086962145344, 4.151533854919492], [119.4683114994199, 168.15413290658947],
                         [214.80336018571938, 194.19889908935804], [81.06381288786969, 258.06654946116294],
                         [297.83389121777117, 29.391171093067456], [122.18086962145344, 4.151533854919492],
                         [142.35589109231393, 170.4254101637603], [199.29047288615527, 177.2180178510058],
                         [104.02017912949572, 259.4826176022963], [299.70057820147537, 6.467046688744627],
                         [145.18086962145344, 4.151533854919492], [165.35589109231393, 170.4254101637603],
                         [186.75345519694272, 157.93530052537008], [127.02017912949572, 259.4826176022963],
                         [277.3926295061564, 0.8674551851599617], [168.18086962145344, 4.151533854919487],
                         [154.33283951150815, 190.61184951910218], [206.22472211849626, 145.69316980928903],
                         [150.02017912949572, 259.4826176022963], [255.3265862658685, 7.355115450443898],
                         [191.18086962145344, 4.151533854919482], [163.3080726537327, 211.78837402249306],
                         [228.2876613520043, 139.19496141169736], [173.02017912949572, 259.4826176022963],
                         [243.17600375466998, 26.88364188329479], [190.7545024302243, 27.147581580958047],
                         [181.46971331483556, 225.90059597713136], [251.2876613520043, 139.19496141169736],
                         [196.02017912949572, 259.4826176022963], [237.2968611277866, 49.11955162345974],
                         [190.67336652791076, 50.147438471064035], [162.24598310083715, 213.27331611726427],
                         [274.2876613520043, 139.19496141169736], [194.0262589755189, 282.39602595678525],
                         [259.0696570136609, 56.532065320718885], [167.72767376416434, 51.72705348484279],
                         [169.94284217955723, 234.94722578585717], [297.2876613520043, 139.19496141169736],
                         [215.26210589952865, 291.2299834742304], [245.3615414822427, 75.00062153330062],
                         [144.85506465701673, 54.14443897988239], [160.7677989986215, 213.85650311858083],
                         [292.1381245535706, 161.61107772923947], [238.26210589952865, 291.2299834742304],
                         [263.15417535730995, 89.57533181473704], [135.02510488280393, 74.93799304928953],
                         [145.3629973054281, 196.7775076916423], [279.57385849577247, 180.8760516048735],
                         [261.26210589952865, 291.2299834742304], [285.61710589824435, 94.51666276025725],
                         [114.20720886982936, 65.15969025212797], [161.059009549804, 213.5892654707802],
                         [283.9010926835257, 203.46531994814526], [284.26210589952865, 291.2299834742304],
                         [298.5779388403095, 75.51622041151498], [111.61765120738747, 88.01344686046019],
                         [145.36485231808737, 196.77577598209413], [297.66867258432177, 221.88959045406207],
                         [298.1476062404017, 272.8944202081724], [296.27861959017133, 98.40099987267527],
                         [96.13976018203589, 105.0262329170513], [162.93642316879973, 211.616257707375],
                         [275.3904756255808, 227.60640252614775], [276.4443016476749, 265.2808422217508],
                         [299.9573407768643, 75.69710129928977], [118.75030411875893, 109.24088626999938],
                         [147.05989383177328, 194.97486905706887], [290.9146853341565, 210.6358718059798],
                         [298.88061290473803, 270.3416659863351], [297.2217785538598, 98.53384141963248],
                         [141.75030411875895, 109.24088626999938], [161.30524901958808, 213.03227350989647],
                         [281.59391181296985, 189.60914640788832], [298.17897762515685, 293.3309614939066],
                         [297.7742788541415, 75.54047838987564], [163.60812130606016, 116.39880690427019],
                         [147.04881972529458, 194.98361085093998], [293.7427679913324, 209.13874685330097],
                         [289.32768637173814, 272.1023335790565], [289.4136178653092, 96.96708212984846],
                         [144.26565056436428, 103.95417651174188], [159.79351418545258, 214.12970087259237],
                         [288.30329939465514, 186.79121496752526], [293.5444452124137, 294.7124849469617],
                         [278.35611284402466, 117.13466955879659], [164.37422066325365, 115.11864732670006],
                         [167.9902371158609, 235.61955273811526], [279.0566880496453, 207.85065889737143],
                         [291.6062090428343, 271.7942991428686], [255.52257517364984, 119.89683491510199],
                         [142.1181581941108, 109.31626132009796], [174.78888384097658, 257.59177162258555],
                         [299.0127314250064, 219.28553243408822], [297.48850510790976, 294.0293748792541],
                         [239.0445550540358, 103.85081195183798], [165.1181581941108, 109.31626132009796],
                         [179.8874760682414, 280.01953025558487], [284.74952251594505, 201.24222698257873],
                         [286.12093843811306, 274.0349149463695], [230.3744849361517, 125.15409536428342],
                         [146.33824026709726, 122.59461523369114], [161.17067633738463, 293.3867067650427],
                         [274.7725565277872, 180.5188066647079], [287.83035684379513, 296.97130282053826],
                         [238.51937762151624, 103.64454578406452], [169.33824026709726, 122.59461523369114]]
    uav_coor_list_GA = [[120, 160], [250, 225], [10, 280], [275, 50], [40, 23], [98.57287239852886, 151.6406816814842],
                        [230.34568644639623, 213.05395635632337], [19.80364984529953, 259.1940285083643],
                        [260.64263196061484, 32.03152808440177], [55.64736678138904, 6.142956581633811],
                        [119.82818613572123, 160.4276969843912], [217.0846248178267, 194.26182384073905],
                        [37.973570896543904, 245.092469410465], [275.9144404976135, 49.22954727293782],
                        [78.52273755382171, 3.7518455378442166], [102.23476555913643, 145.6131246849489],
                        [238.8414136334961, 201.72118979438164], [60.12669671119805, 251.2762398331201],
                        [260.757408627809, 31.930287609653615], [86.74843605927406, 25.23062306584611],
                        [122.27486317885563, 156.90004133176282], [218.84606423241362, 190.35518775634597],
                        [80.88077345962185, 261.1892766191174], [275.0512053419584, 49.94937125712506],
                        [101.58266796409822, 42.80747044510889], [145.18503725382416, 158.93078598696667],
                        [222.53557743289824, 167.6530404494622], [101.5277808852756, 271.3234309679024],
                        [260.78351694180185, 31.909607741046496], [81.23126453171754, 53.52289756363684],
                        [167.29842017877118, 165.25520656237606], [211.15447404238103, 147.66628269302862],
                        [121.26307409254773, 259.5116486289411], [264.8522454219676, 54.546865714455905],
                        [95.95751675601728, 71.19031094042482], [161.03518062560315, 187.38599575525464],
                        [233.65288320697286, 142.88908842624286], [144.18224437406718, 257.58508858401257],
                        [261.22732453771556, 31.83431525038619], [100.67449740223874, 93.70142138800541],
                        [151.32650419229216, 208.23645382967766], [242.6573672114229, 121.72498514229522],
                        [165.88159489134213, 249.9602484461186], [277.803392869432, 47.77903094751504],
                        [122.2649141732348, 85.77337600123498], [173.43155965515467, 214.58991926074535],
                        [252.97517014157125, 101.1691357875587], [182.57437654712223, 265.78273373106833],
                        [294.57978435069356, 63.51283814308774], [142.35985017617537, 74.58438377504575],
                        [152.42395699335248, 205.22612567033335], [273.7104745391023, 111.12137933068658],
                        [179.88629039503434, 288.6251108586563], [299.8272499152316, 85.90623237328401],
                        [149.12817920992939, 52.60280689596716], [173.5930131935546, 214.2189594613407],
                        [253.12799711569062, 100.856798330239], [201.2003591541962, 279.98158883752853],
                        [298.8568146957696, 108.88575054675378], [166.63188205851378, 37.6823381838771],
                        [152.27127782807983, 205.5943666590884], [252.03835658201763, 123.83097260282989],
                        [219.94309018081202, 293.31238152453454], [298.544215166501, 131.88362613417058],
                        [175.44138880577748, 16.43633642190044], [173.3904490654129, 214.70373580564313],
                        [253.0115358729566, 100.85157047684568], [242.7753143416546, 296.08538348433143],
                        [299.97371471206014, 154.83915991252664], [191.89636769912784, 32.50598699742304],
                        [152.862433008603, 204.33066698434655], [252.16462038780412, 123.83597245212033],
                        [256.6464875355877, 277.7389790893577], [278.47592293787824, 163.01503594105822],
                        [212.8279904895783, 22.973559848039972], [173.56099579721095, 214.3591014826147],
                        [252.85198187642465, 100.84624574247975], [275.6943358531877, 264.8479172839941],
                        [288.93997157447177, 183.49682507509155], [215.97902728968504, 45.75668884921918],
                        [150.9991875379962, 209.89090183684814], [253.21675475533308, 123.84335296810299],
                        [262.2915635042197, 246.15659059588177], [287.58813416560344, 206.45706321889102],
                        [218.9684986192713, 68.56158001689595], [170.65880687282635, 197.95359193848444],
                        [252.55171100314152, 100.85296983063286], [280.5399700016947, 260.15643560584215],
                        [283.7746207540136, 183.77541611248307], [215.4466409854295, 45.83282028815249],
                        [148.7255111842855, 204.87678052749715], [251.33213793233142, 123.82061319091157],
                        [261.0418024721372, 247.9571953430508], [290.20749888900843, 205.85749207694587],
                        [219.2059921136942, 68.5235073446172], [138.37232471741365, 184.33872974408098],
                        [252.35267720636705, 100.84326565926312], [281.5666187596219, 258.3365939944661],
                        [288.57433959886146, 182.91554815902543], [214.83024943346928, 45.94358537848858],
                        [119.97382546936049, 170.5367289681287], [251.26917680382823, 123.81773032936367],
                        [297.4419940207613, 274.97908360143305], [285.5458209953592, 205.7152866458643],
                        [218.6710073333968, 68.62063498275025], [98.41261266704625, 162.52960073802518],
                        [252.47883066638107, 100.849562410855], [299.7973685595109, 297.85816161568465],
                        [288.4780772934487, 182.90296819722093], [213.50443325732704, 46.20843936704843],
                        [75.53197059077432, 164.86973282351414], [250.50895598242715, 123.76505048616157],
                        [299.61678209389487, 274.8588705716451], [285.2811139335468, 205.6796981046384],
                        [217.97752669815875, 68.76927789467386], [64.5020610990205, 185.05242582032997],
                        [252.4921720100931, 100.85071317984593], [298.2714533371459, 297.8194910017699],
                        [287.5883387109848, 182.79571432063835], [215.5002154900667, 45.90308168327348],
                        [46.033340812806614, 171.3445313434385], [253.00426940725663, 123.84501152217024],
                        [299.92051889280464, 274.8786849393592], [289.39356370360434, 159.86666805338115],
                        [218.26538457196705, 68.73625579351278]]
    uav_coor_list_random = [[120, 160], [250, 225], [10, 280], [275, 50], [40, 23],
                            [121.20372699358771, 182.9684792993552], [240.2797799799639, 245.84507910184294],
                            [24.18627695266602, 285.8761483133751], [253.12570012521147, 42.89260912937621],
                            [52.52669780534562, 42.28942306274475], [102.59633612296392, 196.4875401020821],
                            [259.56920304270864, 233.3183812964973], [34.628058446675595, 265.38299825704263],
                            [272.63080633680926, 30.704466052012496], [29.582724649369663, 40.68502416662987],
                            [85.23801577784016, 181.39818243530044], [280.8944316977447, 241.9343329450633],
                            [52.50241556018592, 250.90862926289637], [255.5384753508292, 15.314462105758757],
                            [51.799018654018234, 34.732186129271895], [107.3470347844215, 175.05852325150946],
                            [271.90761574249143, 220.76272131565716], [49.699420661867535, 273.7371907506468],
                            [268.18703949791797, 18.585603211049374], [65.95923258650838, 16.607938796317292],
                            [110.15002968273988, 197.88708473925988], [249.49710425243103, 215.58884706574827],
                            [31.092029791243746, 287.25625155337366], [255.99889642055425, 38.09070942264717],
                            [46.66980952376363, 29.13463660166292], [87.23755162662974, 195.88250265606374],
                            [251.90125890758705, 238.46285065921856], [56.18179331580753, 298.9558004261757],
                            [258.0034785037504, 61.00318747875732], [68.54410939855217, 36.24202747228671],
                            [98.3881728922955, 175.76624939185763], [238.70900087151298, 257.30334767786536],
                            [98.87654318390574, 290.65678174825723], [235.7871844991018, 55.05034944139934],
                            [89.86933805358828, 44.85797912085268], [103.95237649108786, 198.08305109620554],
                            [256.83324820446757, 271.4635616103555], [121.19334488825366, 285.0925781494649],
                            [221.31281550495555, 37.17599232788902], [92.2734927087443, 21.983975527382395],
                            [82.07807661629933, 190.97566022558175], [268.33324820446757, 291.3821458973976],
                            [130.74417562153695, 285.59311597850444], [244.2567886609315, 35.57159343177413],
                            [100.88944435731028, 0.6587468723462848], [100.44669334738705, 204.81740575807885],
                            [284.01921048590503, 274.5610107601567], [141.6664745307677, 281.9385658852732],
                            [252.8727403094975, 14.246364776738023], [112.38944435731028, 20.577331159388372],
                            [90.36415697123827, 225.4896688229597], [287.09712318745994, 262.6596054120992],
                            [129.13977672542205, 262.64914282252846], [229.29697402493534, 0.35917713852103184],
                            [130.99683522793407, 34.096391962115256], [89.16042997765055, 202.52118952360448],
                            [287.4282898583328, 270.2445691992261], [125.14586863908265, 285.29972114180924],
                            [248.13747104358214, 13.55143517459509], [109.52448541849843, 25.853929122573348],
                            [99.60221147166013, 223.01433957993694], [289.618724577872, 265.08422838301703],
                            [118.80620945529168, 263.1907021352279], [270.54798253364254, 18.725309424503983],
                            [125.78794138578903, 9.590473155282751], [118.89163453440489, 235.54103738528258],
                            [275.7769790453749, 283.4528451141048], [99.96571243664486, 276.382960171302],
                            [269.74529410948503, 41.711298445943186], [148.70041944189916, 11.595055238478889],
                            [109.53669174366148, 214.52949185950274], [254.7654335195951, 292.80778790484817],
                            [81.35832156602108, 262.8638993685751], [284.2196631036313, 59.585655559453514],
                            [140.49304354676698, 15.68710191017285], [98.38607047799573, 234.64574512370885],
                            [250.41699437835197, 292.08010875352073], [83.7624762211771, 239.98989577510483],
                            [274.8647203128879, 38.57411003367369], [150.21326356680308, 36.5321810120158],
                            [106.25253377448611, 256.2586754017847], [242.5505310818616, 270.4671784754448],
                            [61.04564438748893, 236.3919030791795], [297.7771983689981, 40.57869211686983],
                            [135.1239059000214, 19.17386066689204], [128.36155278106745, 262.5983345855757],
                            [241.3468040882739, 293.4356577748], [45.06850186693199, 252.9367184869685],
                            [282.38719442274436, 57.6710231028499], [137.38617264665174, 18.350462909148355],
                            [145.18268791830837, 278.28429686701315], [240.64367874376617, 296.1544417517633],
                            [41.470509171006675, 230.21988665328033], [279.1862131006628, 80.44718868390602],
                            [159.13309988543602, 25.83853046166296], [142.77853326315235, 255.41029327354286],
                            [244.04569793122957, 298.9588499532386], [25.784546889569214, 247.04102179052126],
                            [287.42867594020476, 58.97483887447038], [158.33041146127852, 2.8525414402237566],
                            [130.9326575402211, 235.69544535739428], [244.78107964423407, 297.0919747150098],
                            [40.87390455635088, 229.6827014453975], [273.9096151374779, 77.58222974509417],
                            [181.88283703920638, 7.644336581058727], [153.9291545288181, 235.29404000933675],
                            [266.39400992231, 289.22551141851943], [58.49292674808737, 214.89858642260708],
                            [295.3819649469135, 85.82469258463607], [180.95369330491485, 6.878409593227882],
                            [133.08407542697515, 245.01426002937285], [263.19302860022844, 266.44934583746334],
                            [77.10031761871116, 201.37952561988018], [288.57053241147344, 107.42779661068545],
                            [158.30311498563407, 10.872317679567278], [154.09562095275498, 235.65931723862946],
                            [260.39003370191006, 289.27790732521373], [88.60031761871116, 221.29810990692226],
                            [290.57511449466955, 84.5153185545753], [149.19114203181414, 9.834139498245666]]
    # 第一步：把所有的设备进行初始化，生成100个地面设备、5个无人机、一个卫星、一个云服务器。
    app_list = []  # 所有传感器的集合
    uav_list = []  # 所有无人机的集合
    app_coor_list = [[168.9992961011875, 148.77895793793846], [68.79043691030662, 252.01596025763644],
                     [264.76915322612126, 209.29275565258146], [261.1465715929035, 36.014262358533024],
                     [96.39899064978124, 118.46986226387428], [232.2709682792418, 251.8932971049062],
                     [299.7663059222159, 163.5641596793262], [229.77326425584062, 245.12133433888073],
                     [27.510532284273392, 117.86056453234374], [21.619683197958583, 156.26054774622455],
                     [5.05526041924681, 151.26200934871733], [120.43469583917496, 33.149867010878296],
                     [126.63886047357316, 258.07076842632245], [65.71413606346364, 22.686471888603432],
                     [194.49439170605748, 255.0522925325961], [146.55134956880653, 31.87917115359964],
                     [142.47274685087547, 156.96636727776374], [188.927588721916, 244.5129777909142],
                     [191.6970645083724, 228.36418295194176], [39.48560765342896, 222.23073225625606],
                     [210.06974231068594, 210.39480347358813], [154.88730257547732, 277.5866408969766],
                     [151.24765003362302, 58.81708212116587], [7.6601971488984955, 153.52958144591457],
                     [59.40839657358934, 254.37337193266717], [89.2579290959439, 138.53200847983715],
                     [276.9323069371984, 58.20880662711577], [232.66315130096243, 253.1671773614607],
                     [209.78253176171398, 37.35044597224568], [81.46514189899601, 39.58962878468998],
                     [34.94112347806313, 273.68193821567576], [50.323200696752494, 101.30017819944817],
                     [61.3221289269547, 186.40831133767102], [131.35513615387086, 113.50936864807198],
                     [241.2715331813307, 241.97149349587437], [40.47408622180559, 255.72306340257285],
                     [128.33871462731088, 268.8624647146435], [190.24010038165935, 259.9842346147468],
                     [137.14993650882414, 72.77674273656254], [3.374209878456269, 268.4308068376326],
                     [175.08856869768024, 33.77471847713842], [142.2893786453823, 200.3671943455782],
                     [91.90813237028263, 247.3035455458755], [86.19656090111782, 159.29236934002185],
                     [61.078597861943805, 51.72919810179859], [83.60173922286887, 299.3268409521438],
                     [206.10568844693492, 141.2920667894033], [26.965228541599974, 158.9550955068711],
                     [54.781834993523226, 233.75481073890737], [91.4052320943551, 113.17241745255193],
                     [195.73841740990542, 127.32538040009116], [161.3340724580552, 69.14763219881563],
                     [73.41449435386295, 2.8189752534782175], [19.473335030513837, 164.42042247914773],
                     [63.10765687415796, 44.919532234519096], [118.94422535764289, 3.7069236500316904],
                     [161.75157408235367, 210.32115429882612], [148.4442220823616, 268.2183492833107],
                     [56.29052697884179, 160.16110590959008], [203.54206185490835, 196.0746387775393],
                     [194.3524998790222, 192.68316956843486], [250.1992815097888, 202.396104689441],
                     [103.0103926381177, 74.81238636315437], [23.71485806910019, 161.01405760218043],
                     [87.49595885243873, 286.8137471156991], [76.32342334878507, 245.91475616753868],
                     [84.9548540672657, 144.93815623255676], [191.4941338962086, 22.888490462906052],
                     [33.02245428885744, 229.877878008148], [100.13484061282351, 292.27495128871647],
                     [105.36994787433433, 135.36872110221745], [208.47469673490372, 172.9968018121175],
                     [237.6946852327302, 248.07601736444445], [201.35861191858882, 220.2806811757061],
                     [24.07961602240263, 134.2469388511351], [148.6396111691499, 236.0584191625767],
                     [184.8000595004617, 36.731020109407396], [238.46952237267726, 262.87169434412505],
                     [157.25563988891494, 200.39330799305603], [113.2589202748508, 42.43924821194991],
                     [245.58212700309005, 294.6377369384179], [39.07991633407354, 216.580914928213],
                     [176.62756594655644, 33.55260340816518], [65.86965408715344, 199.81011643461397],
                     [161.1502139311998, 257.4472184146118], [10.474254729837762, 191.7179086228613],
                     [202.88370329827293, 191.44991278527135], [287.45745272222666, 140.18309090719487],
                     [280.11344905322113, 28.29694181208594], [168.3167007159406, 168.98483106418064],
                     [21.603960620860796, 132.8968543331693], [109.43483133086451, 90.88383552950202],
                     [164.6840244022289, 4.435325581043836], [64.36968171431504, 299.856180400684],
                     [58.2187147154449, 294.7651477956747], [148.66462768588224, 242.68534464784727],
                     [103.75704019872792, 286.4709942217844], [180.96612095000677, 150.93252878147098],
                     [37.66549036626168, 68.60830532529687], [86.91434016361832, 181.89243425699232],
                     [278.43000515512347, 162.63948632065623], [241.44657487133247, 94.61381176032388],
                     [5.443560380843914, 269.4038742469291], [113.78768731072454, 279.7898034375263],
                     [153.63284732792195, 214.35531875788075], [85.36149032434756, 42.34321254477656],
                     [235.9479921676705, 286.28273865137095], [193.36200650346348, 286.77048650789254],
                     [154.81527493475093, 42.74931800555181], [136.46822045006783, 168.14626665954526],
                     [160.8186975321746, 162.1011450091756], [51.611881122772665, 110.98467246851047],
                     [100.32886864963444, 180.3411048339076], [131.27587098232922, 151.79136974039324],
                     [72.89119492811416, 240.6359968853185], [281.65942914171904, 41.21558313579378],
                     [113.70437540600888, 269.1086750957092], [26.335366762135457, 63.50735044424234],
                     [100.70558775811095, 267.62435778256076], [276.11453959858255, 60.22228077472415],
                     [102.57598740304383, 52.165456498941396], [131.24553550861873, 2.901980774399715],
                     [85.36508411475802, 193.67255222039756], [259.3936301071414, 280.9827011347498],
                     [168.31309334414055, 7.914667471976278], [228.0883856926307, 181.98330045763777],
                     [84.60839192400425, 50.1529654297872], [136.1917460358806, 220.58211704591108],
                     [45.720228719050525, 236.69041036652183], [267.08091130656186, 188.2087823005201],
                     [2.954318776389153, 260.85208992169566], [32.28309761587561, 257.5839570344942],
                     [201.1670373259422, 62.215153572947266], [126.97823694941535, 122.77355997836993],
                     [256.1281995191852, 44.42696669332237], [169.39568451067336, 269.10363828714657],
                     [199.8801857528227, 21.375916537462036], [41.229364872414834, 262.98399840083243],
                     [176.7357840928191, 110.5901246179181], [153.1884859365004, 87.73814963578258],
                     [85.79410540287333, 86.64614205668461], [112.79527502764982, 177.4658280726565],
                     [170.47972068678087, 30.151263998694887], [119.87406438179511, 145.18300097487528],
                     [42.07639748591535, 181.85463854120013], [93.30297244796319, 216.81593769085455],
                     [29.227806981469207, 257.6681771085724], [40.033314838487456, 16.518476825859928],
                     [238.40725946323445, 34.41429991059246], [277.2250772597501, 131.15297299306414],
                     [56.79362063292721, 165.51009376223965], [231.4370348515523, 180.6191891653702],
                     [244.7517452658674, 46.063411110258976], [174.21565239099715, 109.68247455118004],
                     [261.8342406178962, 251.78690450492752], [177.75458144443868, 184.56969567027073],
                     [215.0671685575112, 83.55381728516562], [232.10083789614174, 205.5902529557039],
                     [89.15831154592449, 3.1528997780341794], [167.93386765801856, 163.75423823316314],
                     [115.04243658893324, 70.57370574215459], [114.28176139172595, 258.19669795196864],
                     [7.390618382456027, 278.08647121577917], [27.943737165430406, 21.029115107951945],
                     [250.89003946168407, 100.98354919057674], [161.49561746467015, 266.9527440272872],
                     [166.12002058362637, 149.92607991492102], [269.12879568725737, 104.83254997154965],
                     [233.96073685254407, 224.17582253798025], [206.2203168496142, 155.48355879530686],
                     [16.120416588431674, 111.85182323340945], [82.28022794927881, 248.01425239065406],
                     [127.60629775564311, 1.22964992892034], [71.87601721613237, 268.45809517507394],
                     [148.9662474609474, 53.0574994397823], [167.89360469595672, 192.4381552797961],
                     [146.0369496666425, 261.2407284653631], [237.47876457530091, 223.7126401544219],
                     [202.28905650003946, 164.64306046915422], [277.2234416699363, 195.7718148881111],
                     [107.33827248315202, 34.72071569922639], [182.62301709068336, 235.29335985963388],
                     [3.611036284297675, 83.92057090424217], [221.33036793953298, 200.2061349656116],
                     [217.56567113826276, 155.73014603908308], [88.08883858221664, 209.79535009887528],
                     [155.49061896108842, 24.497018178704955], [50.42035839306407, 184.25757194105802],
                     [71.6437982227808, 184.9457620526441], [94.28227362925041, 101.80780110742043],
                     [14.246945723801774, 154.55827967291748], [121.90620606995161, 64.36486948073617],
                     [112.48006693246538, 238.43290512163108], [160.53257841331313, 31.08879176379865],
                     [247.74440929406356, 219.3903775085534], [273.36882698279527, 172.08011506263915],
                     [55.594608554652304, 95.82012681294651], [15.386425375549095, 15.5886895464193],
                     [105.08683869305916, 166.016513916169], [95.90471396258783, 1.3216962712470859]]  # 传感器位置的列表

    uav_coor_list = [[120, 160], [250, 225], [10, 280], [275, 50], [40, 23]]
    for i in range(0, 200):  # 1000个传感器
        app_list.append(Appliances(i))
        app_list[i].setcoor(app_coor_list[i])

    uav = UAV(0)

    UAV_R = 23

    # 所有障碍物的位置
    x_obstacle = [105, 230, 200, 35]
    y_obstacle = [210, 260, 100, 50]
    obstacle_R = [42, 32, 36, 46]
    cover_list = [[], [], [], [], []]  # 无人机覆盖传感器集合
    cover_list_ = []  #
    for j in range(0, len(uav_coor_list_random), 5):
        for i in range(5):
            print('j:{}    i:{}    j+i:{}'.format(j, i, j+i))
            uav.coordinates_x_y = uav_coor_list_random[j+i].copy()
            # length = len(uav.cover(app_list))
            cover_list_ = uav.cover(app_list)
            for k in cover_list_:
                cover_list[i].append(k)

    # # 将cover_list中重复的数据去掉，方便之后统计
    # for i in range(0, 5):
    #     cover_list[i] = uav.unique_list(cover_list[i])
    non_cover_list = []  # 没被无人机覆盖的传感器列表
    for i in range(0, len(app_list)):
        if not app_list[i].flag:
            non_cover_list.append(app_list[i].id)
    # 将cover_list中重复的数据去掉，方便之后统计
    # cover = []
    # for i in range(0, 5):
    #     for id in cover_list[i]:
    #         cover.append(id)
    # cover = list(set(cover))
    # non_cover_list = []  # 没被无人机覆盖的传感器列表
    # for i in range(0, len(app_list)):
    #     if not app_list[i].flag:
    #         non_cover_list.append(app_list[i].id)
    # cover_num = len(cover)